﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace QuickSort
{
	class Program
	{
		/// <summary>
		/// 快序排序平均时间复杂度：N(logN)  最坏的时间复杂度为O(n2)
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			//2次比较
			for (int i = 1; i <= 2; i++)
			{
				List<int> list = new List<int>();
				//随机选择200个数到数组中
				for (int j = 0; j < 200; j++)
				{
					Thread.Sleep(j);
					list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000));
				}
				Console.WriteLine("\n第" + i + "次比较：");
				Stopwatch watch = new Stopwatch();
				watch.Start();
				var result = list.OrderBy(single => single).ToList();
				watch.Stop();
				Console.WriteLine("\n系统定义的快速排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", result.Take(10).ToList()));
				watch.Start();
				new QuickSortClass().QuickSort(list,0,list.Count-1);
				watch.Stop();
				Console.WriteLine("\n自己定义的快速排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", list.Take(10).ToList()));
			}
			Console.ReadLine();
		}
	}

	/// <summary>
	/// 快速排序类
	/// </summary>
	public class QuickSortClass
	{
		/// <summary>
		/// 分割函数
		/// </summary>
		/// <param name="list"></param>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns></returns>
		public int Division(List<int> list,int left,int right)
		{
			//首先选一个基准数据
			int baseNum = list[left];
			while (left<right)
			{
				//从数组的右端开始向前找，一直找到比base小的数为止，(包括跟base相等的数)
				while (left<right &&  list[right]>=baseNum)
				{
					right = right - 1;
				}
				//最终找到了比baseNum小的元素，要做的事情就是此元素放到base的位置 
				list[left] = list[right];
				//从数组的左端开始向后找，一直找到比base大的数为止，(包括跟base相等的数)
				while (left < right && list[right] <= baseNum)
				{
					left = left + 1;
				}
				//最终找到了比baseNum大的元素，要做的事情就是此元素放到最后的位置 
				list[right] = list[left];
			}
			//最后就是把baseNum放到该left的位置
			list[left] = baseNum;
			//最终，以baseNum为基点，发现left位置的左侧数值部分比left小，left位置的右侧部分比left大
			//至此我们完成了第一遍的排序
			return left;
		}

		/// <summary>
		/// 快速排序方法
		/// </summary>
		/// <param name="list"></param>
		/// <param name="left"></param>
		/// <param name="right"></param>
		public void QuickSort(List<int> list,int left,int right)
		{
			//左下标肯定小于右小标，否则就超越了
			if(left < right)
			{
				//对数组进行分隔，取出下次分割的基准标号
				int i = Division(list, left, right);
				//对"基准标号"左侧的一组数据进行递归的切割，以至于将这些数值完整的数据进行排序
				QuickSort(list,left,i-1);
				//对"基准标号"右侧的一组数据进行递归的切割，以至于将这些数值完整的数据进行排序
				QuickSort(list,i+1,right);
			}
		}

	}
}
